package dynamic;

import org.junit.Test;

import java.util.ArrayList;

public class Supermarket {
    private final static int max = Integer.MAX_VALUE;
    private int[][] dist;          //存储最短路径
    private int[][] path;          //存储最短路径的长度
    public ArrayList list = new ArrayList<Integer>();//当前两点间最短的路径
    private int[] minPath;
    private int[][] Arcs;

    public Supermarket(int Arcs[][]) {
        dist = new int[Arcs.length][Arcs[0].length];
        path = new int[Arcs.length][Arcs[0].length];
        minPath = new int[Arcs.length + 1];
        minPath[minPath.length - 1] = max;
        this.Arcs = Arcs;
    }

    public void findCheapestPath(int begin, int end) {

        floyd(Arcs);//核心算法
        list.clear();
        list.add(begin);
        findPath(begin, end);
        list.add(end);
        System.out.println("最短路径：" +list.toString());
    }

    public void findPath(int i, int j) {
        int k = path[i][j];
        if (k == -1)
            return;
        findPath(i, k);
        list.add(k);
        findPath(k, j);
    }

    public int[] getMinLength() {
        for (int i = 0; i < Arcs.length; i++) {
            for (int j = 0; j < Arcs.length; j++) {
                findCheapestPath(j, i);
                if (dist[i][j] == max) {
                    continue;
                } else {
                    minPath[i] += dist[j][i];
                }
            }

        }
        return minPath;
    }
    public void floyd(int[][] Arcs) {
        int n = Arcs.length;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                path[i][j] = -1;            //初始化当前的路径长度表
                dist[i][j] = Arcs[i][j];         //初始化当前的路径表
            }

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != max && dist[k][j] != max && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = k;
                    }
                }
    }
    public int MaxNum(int[] array){
        int minIndex = -1;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] < array[array.length - 1] && array[i] != 0) {
                array[array.length - 1] = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

}